%!Tex Program = xelatex 
\documentclass[a4paper]{article}
%\documentclass[a4paper]{ctexart}
\usepackage{xltxtra}
%\setmainfont[Mapping=tex-text]{AR PL UMing CN:style=Light}
%\setmainfont[Mapping=tex-text]{AR PL UKai CN:style=Book}
%\setmainfont[Mapping=tex-text]{WenQuanYi Zen Hei:style=Regular}
%\setmainfont[Mapping=tex-text]{WenQuanYi Zen Hei Sharp:style=Regular}
%\setmainfont[Mapping=tex-text]{AR PL KaitiM GB:style=Regular}
%\setmainfont[Mapping=tex-text]{AR PL SungtiL GB:style=Regular}

\usepackage{graphicx}
\usepackage{tikz}
\usepackage{pgfplots} 
\usepackage{fontspec}
\usepackage{cite}
\usepackage{geometry} 
\usepackage{amsmath} 
\usepackage{enumitem}
\usepackage{listings}
\usepackage{ctex}
\usepackage{amssymb}

% 接下来是你的其他代码

% 设置中文字体
\setmainfont{AR PL UMing CN}
\geometry{left=20mm,right=20mm,top=20mm,bottom=20mm}

\title{硬币找零问题} 
\author{wangjie}
\begin{document}
\maketitle
\section{项目设计思路}
这段代码是一个用于找零钱的最小数量问题的算法。  
  
1. 输入:首先要求用户输入1美分、5美分、10美分和25美分分别的硬币数量,然后要求输入一个总金额（以美分为单位）。  
  
2. 初始化：创建一个整型数组 $c$，用于存储用户输入的硬币数量。然后创建一个 $\text{vector<int>}$ 类型的变量 $\text{coins}$,用于存储硬币的面额(1, 5, 10, 25)。接着创建一个大小为 $n+1$ 的 $\text{vector<int>}$ 类型的变量 $\text{dp}$，并初始化所有值为 $\text{INT\_MAX}$，用于存储金额为 $i$ 时的最小硬币数。最后创建一个大小为 $(n+1) \times 4$ 的二维 $\text{vector<int>}$ 类型的变量 $\text{matrix}$，用于存储硬币数最小情况下各个面额硬币所剩下的个数。  
  
3. 算法核心：  
   首先，对 $\text{dp}$ 进行初始化，将 $\text{dp}[0]$ 置为 0,表示金额为 0 时不需要硬币。  
   然后，通过两层循环遍历金额从 1 到 $n$ 的所有情况，以及硬币的四种面额。  
   在循环中，通过比较金额是否大于等于当前硬币面额，并且剩余硬币数量大于 0 以及之前金额的最小硬币数不是不可达（$\text{INT\_MAX}$）来更新 $\text{dp}$ 和 $\text{matrix}$.  
  
4. 输出：最后根据 $\text{dp}[n]$ 的值判断是否能凑出总金额，若不行则输出 "无法凑出该金额"，否则输出 "最少需要 $\text{dp}[n]$ 枚硬币"。  
  
这段代码的主要目的是使用动态规划的思想来解决最小找零问题，通过计算最小硬币数量和各种面额硬币的剩余个数来实现找零。  
\section{测试说明}
四个测试数据：\\
1、1美分: 5 ;5美分:0 ;10美分:3 ;25美分:2 ;金额:55 \\
2、1美分: 1 ;5美分:1 ;10美分:1 ;25美分:0 ;金额:17 \\
3、1美分: 0 ;5美分:0 ;10美分:0 ;25美分:0 ;金额:0 \\
4、1美分: 100 ;5美分:50 ;10美分:30 ;25美分:70 ;金额:1000 \\
分别应该对应的输出为 \\
1、最少需要 4 枚硬币 \\
2、无法凑出该金额 \\
3、最少需要 0 枚硬币 \\
4、最少需要 40 枚硬币 \\
时间复杂度应为O(n*m),在这里m=4 \\

\end{document}